package hash;

/**
 * 基于链表的哈希表
 * @author yuisama
 * @date 2022/01/01 18:20
 **/
public class HashTableByLinkedList<K,V> {
    // 节点类定义
    private static class Node<K,V> {
        private K key;
        private V value;
        private Node<K,V> next;

        public Node(K key, V value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    // 实际存储的键值对个数
    private int size;
    // 取模数
    private int M;
    private Node<K,V>[] table;
    // 默认容量
    private static final int DEFAULT_CAPACITY = 16;
    // 默认负载因子
    private static final double LOAD_FACTOR = 0.75;

    public HashTableByLinkedList() {
        this(DEFAULT_CAPACITY);
    }

    public HashTableByLinkedList(int capacity) {
        table = new Node[capacity];
        this.M = table.length;
    }

    /**
     * 将键值对存入哈希表中
     * @param key
     * @param value
     * @return 修改前value
     */
    public V put(K key,V value) {
        // 取得当前key对应的表中索引
        int index = hash(key);
        for (Node<K,V> cur = table[index];cur != null;cur = cur.next) {
            if (cur.key.equals(key)) {
                // 重复元素，更新值
                V oldVal = cur.value;
                cur.value = value;
                return oldVal;
            }
        }
        // 走完循环还没找到，说明此时key不重复，新建结点头插
        Node<K,V> newNode = new Node<>(key,value,table[index]);
        table[index] = newNode;
        size ++;
        // 扩容
        if (size >= LOAD_FACTOR * M) {
            resize();
        }
        return value;
    }

    /**
     * 根据key值取得相应value值
     * @param key
     * @return
     */
    public V get(K key) {
        for (Node<K,V> cur = table[hash(key)];cur != null;cur = cur.next) {
            if (cur.key.equals(key)) {
                return cur.value;
            }
        }
        return null;
    }

    /**
     * 删除哈希表中指定的键值对
     * @param key
     * @param value
     * @return
     */
    public boolean remove(K key,V value) {
        Node<K,V> prev = table[hash(key)];
        if (prev.key.equals(key)) {
            if (prev.value.equals(value)) {
                table[hash(key)] = prev.next;
                size --;
                return true;
            }
        }
        while (prev.next != null) {
            if (prev.next.key.equals(key)) {
                if (prev.next.value.equals(value)) {
                    prev.next = prev.next.next;
                    size --;
                    return true;
                }
            }
            prev = prev.next;
        }
        return false;
    }

    /**
     * 扩容操作
     */
    private void resize() {
        @SuppressWarnings("unchecked")
        Node<K,V>[] newTable = new Node[table.length << 1];
        // 元素搬移
        int oldM = this.M;
        this.M = newTable.length;
        for (int i = 0; i < oldM; i++) {
            Node<K,V> next;
            for (Node<K,V> cur = table[i];cur != null;cur = next) {
                next = cur.next;
                int newIndex = hash(cur.key);
                cur.next = newTable[newIndex];
                newTable[newIndex] = cur;
            }
        }
        this.table = newTable;
    }

    public boolean contains(K key) {
        for (Node<K,V> cur = table[hash(key)];cur != null;cur = cur.next) {
            if (cur.key.equals(key)) {
                return true;
            }
        }
        return false;
    }


    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }
}